11064. Теория чисел

Для заданного натурального числа n найти количество таких m, что 1 £ m £ n и НОД(m, n) ¹ 1, НОД(m, n) ¹ m.

Вход. Каждая строка содержит натуральное число n (0 < n < 2³¹).

Выход. Для каждого входного n вывести количество таких m, которые удовлетворяют выше описанным условиям.

Пример входа

1

2

6

2147000000

Пример выхода

0

0

1

1340599805

РЕШЕНИЕ

теория чисел – функция Эйлера

Анализ алгоритма

Из числа n следует вычесть количество взаимно простых с ним чисел, которое равно функции Эйлера j(n), и количество его делителей (если m является делителем n, то НОД(m, n) = m). При этом число 1 будет одновременно и взаимно простым с n и делителем n. Поэтому к полученной разности следует прибавить 1. Если n = – разложение числа n на простые множители, то оно имеет d(n) = (k₁ + 1) * (k₂ + 1) * … * (k_t + 1) делителей.

Таким образом, количество искомых значений m для заданного n равно

n – j(n) – d(n) + 1

Реализация алгоритма

Функция euler(n) вычисляет функцию Эйлера. Одновременно в переменной common подсчитываем количество делителей числа n по выше приведенной формуле. В цикле при встрече делителя i в переменной div вычисляем степень, с которой i входит в число n. То есть div является максимальной степенью, для которой n делится на i^div.

int euler(int n)

{

int i, result = n, div;

common = 1;

for(i = 2; i <= sqrt(1.0*n); i++)

if (n % i == 0)

{

div = 0;

result -= result / i;

while (n % i == 0) {n /= i; div++;}

common *= div + 1;

}

if (n > 1) {result -= result / n; common *= 2;}

return result;

}

Основной цикл программы. Для каждого входного n вычисляем результат n – j(n) – common + 1, где common = (k₁ + 1) * (k₂ + 1) * … * (k_t + 1), и выводим его.

while(scanf("%d",&n) == 1)

{

res = n - euler(n) - common + 1;

printf("%d\n",res);

}